package algorithms.leaning.class17;

import common.util.MyUtil;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 打印一个字符串的全部子序列，要求不要出现重复字面值的子序列
 *
 * @author guichang
 * @date 2021/6/16
 */

@SuppressWarnings("all")
public class Code4_递归_字符串子序列 {

    public static void main(String[] args) {
        String str = "aabcc";
        MyUtil.print(subsequence(str));
    }

    public static List<String> subsequence(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
        Set<String> set = new HashSet();
        process(set, str.toCharArray(), 0, "");
        return new ArrayList<>(set);
    }

    private static void process(Set<String> set, char[] cs, int index, String path) {
        if (index == cs.length) {
            set.add(path);
            return;
        }
        // 没选index
        process(set, cs, index + 1, path);
        // 选了index
        process(set, cs, index + 1, path + cs[index]);
    }

}